home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000023_icon-group-sender _Tue Dec 20 06:36:10 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  11KB
  1. Received: by cheltenham.cs.arizona.edu; Tue, 20 Dec 1994 01:18:11 MST
  2. To: icon-group-l@cs.arizona.edu
  3. Date: 20 Dec 1994 06:36:10 GMT
  4. From: Will Mengarini <mengarini@delphi.com>
  5. Message-Id: <3d5u0q$ocp@news.halcyon.com>
  6. Organization: Northwest Nexus Inc.
  7. Sender: icon-group-request@cs.arizona.edu
  8. References: <dkuhlmanD0wuqE.I5w@netcom.com>
  9. Subject: Re: Backtracking in Icon
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12. dkuhlman@netcom.com (G. David Kuhlman) writes:
  13.  
  14. >[...] in spite of the fact that I have a language
  15. >with a strong backtracking mechanism, I find that I
  16. >don't use it much, except of course, for trivial
  17. >constructs like
  18. >    (checkValid(x) | write("error"))
  19. >which I feel I have to write instead of an
  20. >'if' statement so that I can feel like a cool Icon programmer.
  21. >I'd be interested to know if others use backtracking more heavily [...]
  22.  
  23. Here are two Icon programs that backtrack for parsing.
  24. I hope their length doesn't inconvenience anybody; I thought they
  25. were worth posting because the backtracking control structures look
  26. weird, & I'd be interested in seeing how other people prettyprint theirs.
  27.  
  28. ----------------------------------<snip>----------------------------------
  29. #        FNortPth.Icn (Full Norton Path) - Will Mengarini - 10 Aug 92
  30.  
  31. #  Filter Norton FA | FS output so each line is 1 full file path
  32.  
  33. #  Sample FA output excerpts preceded by column-ruler line:
  34. #
  35. #  123456789012345678901234567890
  36. #   D:\-\I
  37. #       deldupln.icn
  38. #       fnortpth.icn  Archive
  39. #       gug           Archive
  40. #
  41. #     33 files shown
  42. #     no files changed
  43. #
  44. #   D:\-\I\^
  45. #       deldupln.asv
  46. #       deldupln.icn  Archive
  47. #       reverse.icn
  48. #       scrap.b       Archive
  49. #       _.rst         Archive
  50. #
  51. #     9 files shown
  52. #     no files changed
  53. #
  54. #   Total of all files
  55. #     42 files shown
  56. #     no files changed
  57.  
  58. #  Sample FS output excerpts preceded by column-ruler line:
  59. #
  60. #  123456789012345678901234567890
  61. #    D:\-\I
  62. #      whug              1,344 bytes
  63. #      fnortpth.icn        215 bytes
  64. #
  65. #         30,272 total bytes in 33 files
  66. #         77,824 bytes disk space occupied, 61% slack
  67. #
  68. #    D:\-\I\^
  69. #      deldupln.asv      1,122 bytes
  70. #      deldupln.icn      1,058 bytes
  71. #
  72. #         12,399 total bytes in 9 files
  73. #         24,576 bytes disk space occupied, 50% slack
  74. #
  75. #    Total of all files found
  76. #         42,671 total bytes in 42 files
  77. #        102,400 bytes disk space occupied, 58% slack
  78. #
  79. #   Drive usage
  80. #     33,435,648 bytes available on drive D:
  81. #     12,103,680 bytes unused on drive D:, 36% unused
  82.  
  83. procedure main()
  84.    while read() ?(
  85.       # All & only lines containing "\\" are directories. They begin (after
  86.       # leading whitespace) with the drive letter, & end with "\\" only if
  87.       # they specify the root. There are no other words on such lines.
  88.       tab(many(' ')),
  89.       dir := tab(upto('\\')) || tab(0) || (move(-1) ~== "\\" | "")
  90.    )|(
  91.       # Lines containing file names begin with leading whitespace. Then
  92.       # come the name & extension as a single word with a separating ".";
  93.       # there's no whitespace between the name & extension, unlike the
  94.       # columnar format of FI & Dir. If the extension is empty, the "." is
  95.       # omitted. In FS, all file names are on lines ending with "bytes"; no
  96.       # other lines end with "bytes". In FA, file names are followed by a
  97.       # list of attributes like "Archive"; no other lines contain the words
  98.       # denoting those attributes; the list may be empty, in which case the
  99.       # line has only 1 word; no other lines have only 1 word except
  100.       # directory lines. Therefore, file names are all & only the initial
  101.       # words on lines that either have no other words & are not directory
  102.       # lines, | end with "bytes" | a word denoting an attribute.
  103.       ((
  104.          (
  105.             tab(many(' ')), tab(many(~' \\')), pos(0)
  106.                # We already know this isn't a directory line since control
  107.                # can't get this far unless the alternative that handles
  108.                # directory lines fails. However, the code is more robust if
  109.                # it doesn't depend on that, & inserting an extra char in a
  110.                # cset entails no extra run-time computation.
  111.          )|(
  112.             reverse(&subject) ? match(reverse(
  113.                "bytes" | "hive" | "d-Only" | "dden" | "stem"
  114.             ))
  115.          )
  116.       ) & &pos:=1 & (
  117.          tab(many(' ')), write(  dir || tab(upto(' ')|0)  )
  118.       ))
  119.    )|1
  120. end
  121. ----------------------------------<snip>----------------------------------
  122. #                  IconGrp.Icn - Will Mengarini - 20 Oct 93
  123.  
  124. # Takes a //cs.arizona.edu/.../icon/newsgrp/*.txt, which is unthreaded, &
  125. # rewrites it in threaded order. The [input, output] file is arg[[1,2]].
  126.  
  127. # A 2-level ISAM is required to get everything right. First, index file 1
  128. # is written with each line corresponding to a message in the download.
  129. # Sorting this file by subject groups together all messages for each thread.
  130. # Then, index file 2 is written with each line corresponding to an entire
  131. # thread of messages. Index file 1 is then rewritten with the threads still
  132. # grouped, but now in chronological rather than alphabetical order; finally,
  133. # the same rewriting routine (procedure lookup) is used for the target file.
  134.  
  135. # All this temporary data is kept in temporary files on disk rather than
  136. # in RAM, so large newsgroup files can be threaded.
  137.  
  138. # The top line of each article is assumed & required to be the line that
  139. # begins with the heading "From icon-group-sender". This line not only marks
  140. # the beginning of an article, it also contains the date in a consistent
  141. # format, whereas "Date: " lines' formats vary.
  142.  
  143. # This program was developed on a MS-DOS system, & requires the presence
  144. # of a sort utility that can accept I/O redirection using "<" & ">", & can
  145. # be told the starting column of the sort key using a syntax like
  146. # "/+41" (to start in column 41). If you want to run on a different system
  147. # that has a system sort with these functions but a different invocation
  148. # syntax, you need to change the 2 system() calls in main().
  149. # The temporary files have names ending in ".tmp".
  150.  
  151. global subjectLength, whenLength, startAtLength, linesLength
  152.  
  153. procedure main(arg)
  154.  
  155.    subjectLength  := 40
  156.    whenLength     := 14
  157.    startAtLength  := 12
  158.    linesLength    := 05
  159.  
  160.    arg[1] || arg[2] | stop( "Usage: IconGrp <input file> <output file>" )
  161.  
  162.    write( "Writing index file 1" )
  163.    index1( arg[1], "IcnGrp1a.tmp" )
  164.  
  165.    write( "Sorting index file 1" )
  166.    system( "sort <IcnGrp1a.tmp >IcnGrp1b.tmp" )
  167.  
  168.    write( "Writing index file 2" )
  169.    index2( "IcnGrp1b.tmp", "IcnGrp2a.tmp" )
  170.  
  171.    write( "Sorting index file 2" )
  172.    system( "sort <IcnGrp2a.tmp >IcnGrp2b.tmp /+" || subjectLength + 1 )
  173.  
  174.    write( "Using index file 2 to rewrite index file 1" )
  175.    lookup( "IcnGrp2b.tmp", "IcnGrp1b.tmp", "IcnGrp1c.tmp" )
  176.  
  177.    write( "Using index file 1 to rewrite BBS file" )
  178.    lookup( "IcnGrp1c.tmp", arg[1], arg[2] )
  179.  
  180.    write( "IconGrp finished." )
  181. end
  182.  
  183. procedure writeIndexLine( out, subject, when, startAt, lines )
  184.    writes( out, left(   subject,    subjectLength  ) )
  185.    writes( out, left(   when   ,    whenLength     ) )
  186.    writes( out, right(  startAt,    startAtLength  ) )
  187.    write ( out, right(  lines  ,    linesLength    ) )
  188.    return
  189. end
  190.  
  191. procedure index1( in, out )
  192.  
  193.    months := ["jan","feb","mar","apr","may","jun",
  194.               "jul","aug","sep","oct","nov","dec",""]
  195.  
  196.    in  := open( in,  "r" ) | stop( "Couldn't open " || in )
  197.    out := open( out, "w" ) | stop( "Couldn't open " || out )
  198.  
  199.    lineNumber := 0
  200.  
  201.    while at := where(in) & line := !in & lineNumber +:= 1 do {
  202.       line ? ((
  203.  
  204.          = "From icon-group-sender",
  205.          #
  206.          # Write data for previous article if there was one
  207.          #
  208.          if writeIndexLine( out, subject, when, startAt, \lines ) then {
  209.             write( "   index1: at = ", at )
  210.          } else {
  211.             "do not fail"
  212.          },
  213.          lines := 0, startAt := at,
  214.          #
  215.          # Parse the date; the line looks like
  216.          #     From icon-group-sender  Thu Mar 18 12:24:03 1993
  217.          # We are here --------------^
  218.          #
  219.          map(tab(0)) ? (
  220.             tab(find( months[month := (1 to *months)] )),
  221.                # We're now at the *start* of the month name
  222.             tab(many(~' ')), tab(many(' ')),
  223.             date := tab(many(&digits)), tab(many(' ')),
  224.             time := tab(many(~' ')), tab(many(' ')),
  225.             year := tab(0)
  226.          ),
  227.          if month = 13 then {
  228.             stop("Month not found on line # ",lineNumber)
  229.          } else {
  230.             when := year[3:0] || " " || right(month,2,"0") || " " ||
  231.                     right(date,2,"0") || " " || time[1+:5]
  232.          }
  233.  
  234.       )|(
  235.  
  236.          ="Subject: ", subject := tab(0),
  237.          #
  238.          # Extract the subject (which will define the thread)
  239.          #
  240.          (  map(subject) ?
  241.             (= "re:", tab(many(' ')), subject[1:&pos] := "")
  242.          )|(
  243.             "do not fail"
  244.          )
  245.  
  246.       ))
  247.       lines +:= 1
  248.    }
  249.  
  250.    writeIndexLine( out, subject, when, startAt, lines )
  251.    every close( in | out )
  252. end
  253.  
  254. procedure index2( in, out )
  255.    in  := open( in,  "r" ) | stop( "Couldn't open " || in )
  256.    out := open( out, "w" ) | stop( "Couldn't open " || out )
  257.    while at := where(in) & line := !in do {
  258.       if subject ~=== line[1+:subjectLength] then {
  259.          write( "   index2: at = ", at )
  260.          writeIndexLine( out, \subject, when, startAt, lines )
  261.          line ? (
  262.             subject := move(subjectLength), 
  263.             when := move(whenLength)
  264.          )
  265.          lines := 0; startAt := at
  266.       }
  267.       lines +:= 1
  268.    }
  269.    writeIndexLine( out, subject, when, startAt, lines )
  270.    every close( in | out )
  271. end
  272.  
  273. procedure lookup( index, in, out )
  274.    index    := open( index,  "r" ) | stop( "Couldn't open " || index    )
  275.    in       := open( in,     "r" ) | stop( "Couldn't open " || in       )
  276.    out      := open( out,    "w" ) | stop( "Couldn't open " || out      )
  277.    every !index ? (
  278.       move(subjectLength + whenLength),
  279.       at := move(startAtLength),
  280.       lines := move(linesLength)
  281.    ) do {
  282.       write( "   lookup: at == \"", at, "\", lines == \"", lines, "\"" )
  283.       seek( in, at )
  284.       every 1 to lines do write( out, read(in) )
  285.    }
  286.    every close( index | in | out )
  287. end
  288.  
  289. ----------------------------------<snip>----------------------------------
  290.  
  291. Will Mengarini      <mengarini@delphi.com>      Be gentle, I'm from Delphi
  292.     "(sorry, I can't figure out how to edit with this mail-reader)"
  293.       --Marvin Minsky, quoted by Tom Maddox <tmaddox@halcyon.com>
  294.